Most computer programs require dynamic memory allocation because the exact memory requirements needed during execution cannot typically be predicted prior to execution. Normally, a program specifies an initial amount of memory that is needed before execution starts. During execution, the program invariably requires more memory, depending on the input data it has to process or a number of other possible factors.
Ideally, the program would accurately predict how much memory it would use during execution. However, static prediction techniques are inefficient because they must conservatively estimate the worst-case maximum amount of memory that will ever be needed under all executions of the program.
As a result, software systems allow programs to specify their memory needs dynamically, and to enlarge or reduce the amount of in-use memory as needed. A "memory manager" is a software module that is in charge of handling memory allocations and deallocations for one or more application programs. Typically, the memory manager is incorporated into the computer operating system because main memory is a resource that is divided among a number of programs running on top of the operating system.
When an application program needs additional memory, it sends a request to the memory manager. In response, the memory manager allocates a memory block of a certain size for use by the program. The program can ask for the actual size of the allocated memory block, request a reallocation of the block to a larger or smaller size, and request other statistical or bookkeeping information from the memory manager. When the program finishes with the block, the memory manager deallocates the block to free that block for other uses. The primary goal of the memory manager is to efficiently perform these management tasks (i.e., allocation, reallocation, deallocation, and bookkeeping) while minimizing wasted space without undue time overhead.
There are many different types of memory managers. Perhaps the best known conventional memory manager is one that utilizes free lists. Free-list memory managers are widely used for managing addressable core memory, such as RAM (Random Access Memory). Another well-known type of memory manager is one that utilizes a bitmap to manage memory space. The bitmap memory manager is primarily used for special situations in which block size is fixed, such as managing disk memory. Bitmap memory managers have not been traditionally used to manage core memory. These two types of memory manager are discussed separately below.
Conventional Free-List Memory Manager
A free-list memory manager maintains a set of free lists that identify different size blocks of free memory space within a memory heap. In this context, the term "heap" means a pool of memory available for the allocation and deallocation of arbitrary-sized blocks of memory in arbitrary order.
FIG. 1 shows a conventional free-list memory manager 20 that manages a memory heap 22. The memory manager 20 maintains a free list 24 that identifies different sizes of free memory blocks in the memory heap 22. In this example, the free list 24 tracks blocks in various sizes that increase at a rate of a power of two, such as 16-byte, 32-byte, 64-byte, . . . , 1 page, and more than 1 page.
The free list 24 maintains entry pointers into the memory heap 22. Here, the free list 24 has an entry pointer 26 for a free 16-byte block A in the memory heap 22. The free block A maintains a pointer 28 to another free 16-byte block B within the heap 22. In this manner, one entry pointer 26 in the free list 24 eventually leads to all free 16-byte blocks in the heap 22. The free list 24 also maintains similar pointers for larger size blocks.
When asked to allocate a block of a given size, the memory manager 20 scans the free list 24 for a suitable candidate block. The memory manager 20 follows the entry pointer into heap 22 and allocates one block to the requesting program. Subsequently, when the program is finished with the block, the memory manager 20 deallocates the block and places it back on the free list 24 by adding the appropriate pointers.
One problem encountered by conventional free-list memory managers is "fragmentation". Block deallocations tend to create a disjoint array of free and in-use blocks within the heap. Over time, the fragmentation becomes more severe. As a result, there are fewer large blocks of memory available for allocation. Entries on the free list 24 tend to migrate toward smaller size blocks, as larger size blocks become extinct.
To combat excessive fragmentation, memory managers typically perform a process known as "coalescing", which attempts to combine smaller free blocks into larger free blocks for more efficient allocation. There are many techniques for coalescing, and this concept is well-understood in the art.
FIG. 2 shows one exemplary coalescing process that utilizes block headers. In FIG. 2, each block 30 in the heap has a header 32 and a data portion 34. The header 32 contains information on the size of the block and whether the block is free or in-use.
During coalescing, the memory manager examines the header of a first free block (e.g., 30(1)) and traverses forward in the heap by the size amount of the first block to the next block (e.g., 30(2)). The memory manager then looks at the header of the next block 30(2) to determine whether that block is free. If free, the memory manager combines the two blocks and forms a single header for the bigger unified block 30(1+2). The memory manager then continues to the next block in the heap, and so on. Unfortunately, this coalescing process is both time-consuming and unidirectional.
To improve speed and enable bi-directional processing, each block header might further be equipped with information indicating whether the preceding block is free. FIG. 3 shows a portion of a heap having free blocks 40. Each block 40 has a header 42 with size and use information for the local block, as well as use information for the preceding block, and a data portion 44. The use information for the preceding block is updated when the state of the preceding block is changed. In addition, each free block 40 has a trailer 46 positioned at the end of the data portion 44 to specify its block size, indicating that the free block can hold a data portion that is at the very least as large as the block size.
During coalescing, the memory manager examines the header of a free block (e.g., 40(2)) to determine whether it is free and whether the preceding block is free. If both are free, the memory manager moves backward to the trailer 46 of the preceding block (e.g., 40(1)) to learn the size of the preceding block. The memory manager combines the two free blocks and forms a new header to create a unified block 40(1+2). With the block structure of FIG. 3, the memory manager can also traverse forward in the heap according to the process described with reference to FIG. 2.
One drawback of this coalescing technique is that the block structure comes at a cost of inefficient space overhead. The headers consume memory space that could otherwise be used for data.
Another drawback concerns alignment. For 64 bit integers, for example, the data portion of the memory block structure must align on 8 byte boundaries; otherwise the processor might generate an unaligned trap. Some processors might accept the unaligned data, but with a considerable performance cost. As a result, the end of the header needs to align at 64 bits. As the amount of header information grows (i.e., by adding information on preceding or succeeding blocks), the header itself must grow at 8 byte increments. As a result, there may be more space reserved for the header than is actually needed, just for alignment purposes. This leads to further inefficient utilization of memory resources.
The technology trend is for processors to increase in speed much more rapidly than the memory system. To an application program, future memory systems will appear increasingly slow. The only component of the memory hierarchy that is expected to keep pace with the processor speed is the cache subsystem, primarily because it is implemented inside the processor itself.
The free list management technique does not perform well with respect to this technological trend. A memory block typically spans multiple cache lines. The traversal of a free list involves fetching at least one new cache line per candidate block. As a result, the free list approach tends to result in an inefficient use of the cache. Additionally, when reading a block, the cache must waste space to hold the header and trailer, which is useless outside the context of coalescing.
Conventional Bitmap Memory Manager
FIG. 4 shows a conventional bitmap memory manager 50 that is typically employed to manage disk memory, as represented by memory 52. Each block in the memory 52 is of equal size. The memory manager maintains a bitmap 54 to identify free and used blocks in the memory 54. There is a one-to-one correspondence between a bit in the bitmap 52 and a block in the memory 54. The bit is set to one binary value when the corresponding block is free and to another binary value when the corresponding block is in use. It is noted that the bitmap 54, although shown within memory manager 50, may be stored on one of the blocks in the memory 52.
When a request for memory is received, the memory manager 50 scans the bitmap 54 to locate one or more free blocks. The memory manager 50 then allocates those block(s) and changes the corresponding bit to indicate that the block(s) are now in use.
One of the drawbacks of the conventional bitmap memory manager 50 is that it cannot accommodate arbitrary size blocks. Inherent in the conventional bitmap-centric architecture is a requirement that the memory blocks all be the same size. Conventional disk memories, for example, are configured with fixed size blocks. Accordingly, the memory manager is left only with the responsibility of allocating and deallocating blocks. There is no block reallocation task, because the fixed-size blocks never need enlarging or shrinking. As a result, the bitmap memory manager 50 has not traditionally been employed for managing addressable core memory, but rather has been used exclusively for disk memory.
For additional background on conventional memory managers, the reader is directed to an article entitled "Dynamic Storage Allocation: A Survey and Critical Review" by Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. This article was published as Springer Verlag Lecture Notes in Computer Science in Proceedings of the 1995 International Workshop on Memory Management, Kinross, Scotland, UK, September 1995. This article is incorporated by reference.
Accordingly, there remains a need for a core memory manager that addresses the problems of the free list memory manager (i.e., space overhead for header, time cost for coalescing process, inefficient utilization of cache, memory alignment). Furthermore, unlike allocating conventional disk memory, it is desirable that the memory manager be capable of allocating arbitrary size blocks without restriction.